class Solution {
public:
    unordered_map<int, unordered_map<int, pair<int, double>>> dp;
    double n;
    double champagneTower(int poured, int query_row, int query_glass) {
        n = poured;
        if (!n) return 0;
        if (query_glass == 0 && query_row == 0) return 1;
        double ans = dfs(query_row - 1, query_glass) + dfs(query_row - 1, query_glass - 1);
        return ans > 1 ? 1 : ans;
    }
    double dfs(int i, int j)
    {
        if (dp[i][j].first) return dp[i][j].second;
        if (i == 0 && j == 0) return (n - 1) / 2;
        if (j < 0 || j > i) return 0;
        double ans = dfs(i - 1, j) + dfs(i - 1, j - 1);
        ans > 1 ? ans = (ans - 1) / 2 : ans = 0;
        dp[i][j].first = 1;
        dp[i][j].second = ans;
        return ans;
    }
};